package com.LeetCode.DFS;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 路径总和 Ⅱ
 */
public class TreePathSum {

    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        ArrayList<Integer> path = new ArrayList<>();
        dfs(path,sum,root);
        return res;
    }

    public void dfs(List<Integer> path, int target, TreeNode root){
        if(root == null)
            return;
        target -= root.val;
        path.add(root.val);
        if(target == 0 && root.left == null && root.right == null){
            res.add(new ArrayList<>(path));
        }
        dfs(path, target, root.left);
        dfs(path, target, root.right);
        path.remove(path.size()-1);

    }

    @Test
    public void test(){
        TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(8);
        TreeNode node4 = new TreeNode(11);
        TreeNode node5 = new TreeNode(13);
        TreeNode node6 = new TreeNode(4);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(2);
        TreeNode node9 = new TreeNode(5);
        TreeNode node10 = new TreeNode(1);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node3.left = node5;
        node3.right = node6;
        node4.left = node7;
        node4.right = node8;
        node6.left = node9;
        node6.right = node10;

        for(List<Integer> list : pathSum(node1,22)){
            System.out.println(list);
        }
    }
}
